package faction.quickSort;

import java.util.stream.IntStream;

public class QuickSort {

    public void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 当前树
            int base = exec(arr, low, high);;
            // 左子树
            quickSort(arr, low, base - 1);
            // 右子树
            quickSort(arr, base + 1, high);
        }
    }

    // 用最后一位作为标杆思路清晰
    public int exec(int[] arr, int low, int high) {
        // 标记当前区间最前端
        int baseIndex = low;
        // 将标杆提取出来
        int baseValue = arr[high];
        for(;low < high; low++) {
            // 将比baseValue小的提取到前面
            // baseIndex标记着当前比baseValue大的值
            if (arr[low] < baseValue) {
                int temp = arr[baseIndex];
                arr[baseIndex] = arr[low];
                arr[low] = temp;
                baseIndex++;
            }
        }
        arr[high] = arr[baseIndex];
        arr[baseIndex] = baseValue;
        return baseIndex;
    }

    public static void main(String[] args) {
        int[] arr = {16, 1, 12, 18, 11, 13, 2, 2, 5, 6};
        QuickSort quickSort1 = new QuickSort();
        quickSort1.quickSort(arr, 0, arr.length - 1);
        IntStream of = IntStream.of(arr);
        of.forEach(c -> System.out.printf("%s ", c));
    }
}